package JAVAcollectionsanddatastructures.Sort;

import java.util.Stack;

public class MySort {

    //直接插入排序
    //平均时间复杂度O（n^2）,最好情况O(n),即在有序的情况下，数据越有序，排序越快
    //空间复杂度O(1)
    //稳定性：是稳定的
    public void insertSort(int[] array) {
        for (int i = 1; i < array.length; i++) {
            int tmp = array[i];
            int j = i - 1;
            for (; j >= 0; j--) {
                if (array[j] > tmp) {
                    array[j + 1] = array[j];
                } else {
                    break;
                }
            }
            array[j + 1] = tmp;
        }
    }


    //希尔排序：插入排序的优化
    //时间复杂度（和增量有关）：o（n^1.3-n^1.5）
    //空间复杂度：o（1）
    //稳定性：不稳定  如果发生跳跃式的交换那么就是不稳定的排序
    public void shellSort(int[] array) {
        int gap = array.length / 2;
        while (gap > 1) {
            shell(array, gap);
            gap = gap / 2;
        }
        shell(array, 1);
    }

    public void shell(int[] array, int gap) {
        for (int i = gap; i < array.length; i++) {
            int tmp = array[i];
            int j = i - gap;
            for (; j >= 0; j = j - gap) {
                if (array[j] > tmp) {
                    array[j + gap] = array[j];
                } else {
                    break;
                }
            }
            array[j + gap] = tmp;
        }
    }


    //选择排序：
    //时间复杂度：o（n^2）
    //空间复杂度：o（1）
    //稳定性：不稳定
    public void selectSort(int[] array) {

        //有序区间: [0, array.length - i)
        //无序区间: [array.length - i, array.length)
        for (int i = 0; i < array.length; i++) {
            for (int j = i + 1; j < array.length; j++) {
                if (array[j] < array[i]) {
                    int tmp = array[i];
                    array[i] = array[j];
                    array[j] = tmp;
                }
            }
        }
    }

    //优化版：记录最小值再与其交换
    public void selectSort1(int[] array) {
        for (int i = 0; i < array.length; i++) {
            int minIndex = i;
            for (int j = i + 1; j < array.length; j++) {
                if (array[j] < array[minIndex]) {
                    minIndex = j;
                }
                int tmp = array[i];
                array[i] = array[minIndex];
                array[minIndex] = tmp;
            }
        }
    }


    //冒泡排序：优化版 设置一个标签位来记录是否进行过交换
    public void bubbleSort(int[] array) {
        //趟数
        for (int i = 1; i <= array.length - 1; i++) {
//            boolean flg = false;
            //下标
            for (int j = 0; j <= array.length - 1 - i; j++) {
                if (array[j] > array[j + 1]) {
                    int tmp = array[j + 1];
                    array[j + 1] = array[j];
                    array[j] = tmp;
//                    flg = true;//如果当趟循环进行过交换，就需要将标志位设置为true
                }
//                if (flg == false) {//如果标志位为false，说明该趟并没有进行交换，该数组已经有序，后续就不需要进行重复步骤了
//                    break;
//                }
            }
        }
    }


    //堆排序***************************


    //快速排序**************************

    /**
     * 时间复杂度：
     * 最好【每次可以均匀的分割待排序序列】：O(K*N*logn)
     * 最坏：数据有序 或者逆序的情况 O(N^2)
     * 空间复杂度：
     * 最好：O(logn)
     * 最坏：O(n)   单分支的一棵树
     * 稳定性：不稳定的排序
     */


    //挖坑法快速排序：基本思路和Hoare 法一致，只是不再进行交换，而是进行赋值（填坑+挖坑）
    public void quickSort(int[] array) {
        quick(array, 0, array.length - 1);
    }

    public void quick(int[] array, int left, int right) {
        //[left,end]是待排序的区间
        if (left >= right) {
            return;
        }
        int pivot = partition(array, left, right);//基准
        quick(array, left, pivot - 1);
        quick(array, pivot + 1, right);
    }

    private int partition(int[] array, int start, int end) {
        //start和end分别是0和length-1
        int tmp = array[start];
        while (start < end) {
            //在右边找比基准小的
            while (start < end && array[end] >= tmp) {
                end--;
            }
            //end下标就遇到了 < tmp的值
            array[start] = array[end];
            //在左边找比基准大的
            while (start < end && array[start] <= tmp) {
                start++;
            }
            //start下标就遇到了 > tmp的值
            array[end] = array[start];
        }
        array[start] = tmp;
        return start;
    }




    //快速排序优化思路*******************************************
    //1.partition 过程中把和基准值相等的数也选择出来

//    2.待排序区间小于一个阈值时，使用直接插入排序
//    public void insertSort2(int[] array,int start,int end) {
//        for (int i = 1; i <= end; i++) {
//            int tmp = array[i];
//            int j = i-1;
//            for (; j >= start ; j--) {
//                if(array[j] > tmp) {
//                    array[j+1] = array[j];
//                }else {
//                    //array[j+1] = tmp;  只要j回退的时候，遇到了 比tmp小的元素就结束这次的比较
//                    break;
//                }
//            }
//            //j回退到了 小于0 的地方
//            array[j+1] = tmp;
//        }
//    }
//    public void quick1(int[] array,int left,int right) {
//        if(left >= right) {
//            return;
//        }
//        //0、如果区间内的数据，在排序的过程当中，小于某个范围了，可以使用直接插入排序  0  1  2 3
//        if(right-left+1 <= 40) {
//            //使用直接插入排序
//            insertSort2(array,left,right);
//            return;
//        }
//
//        //3、********找基准之前，我们找到中间大小的值--使用三数取中法*************
//        int midValIndex = findMidValIndex(array,left,right);
//        swap(array,midValIndex,left);
//
//        int pivot = partition(array,left,right);//基准
//        quick(array,left,pivot-1);
//        quick(array,pivot+1,right);
//    }
//
//    private static int findMidValIndex(int[] array,int start,int end) {
//        int mid = start + ((end-start) >>> 1);
//        if(array[start] < array[end]) {
//            if(array[mid] < array[start]) {
//                return start;
//            }else if(array[mid] > array[end]) {
//                return end;
//            }else {
//                return mid;
//            }
//        }else {
//            if(array[mid] > array[start]) {
//                return start;
//            }else if(array[mid] < array[end]) {
//                return end;
//            }else {
//                return mid;
//            }
//        }
//    }


    //快速排序非递归
    public void quickSort1(int[] array) {
        Stack<Integer> stack = new Stack<>();
        int left = 0;
        int right = array.length - 1;
        int pivot = partition(array, left, right);
        if (pivot > left + 1) {
            //左边有2个元素,如果只有一个元素就说明最左边已经有序了
            stack.push(left);
            stack.push(pivot - 1);
        }
        if (pivot < right - 1) {
            //右边有2个元素
            stack.push(pivot + 1);
            stack.push(right);
        }

        while (!stack.isEmpty()) {
            right = stack.pop();
            left = stack.pop();

            pivot = partition(array, left, right);

            if (pivot > left + 1) {
                //左边有2个元素
                stack.push(left);
                stack.push(pivot - 1);
            }
            if (pivot < right - 1) {
                //右边有2个元素
                stack.push(pivot + 1);
                stack.push(right);
            }
        }

    }


    //合并两个有序数组
    public int[] mergeArray(int[] array1,int[] array2){
        if (array1 == null && array2 == null){
            return null;
        }
        int[] array3 = new int[array1.length + array2.length];
        int index = 0;

        int start1 = 0;
        int end1 = array1.length-1;

        int start2 = 0;
        int end2 = array2.length-1;

        while (start1 <= end1 && start2 <= end2){
            if (array1[start1] <= array2[start2]){
                array3[index] = array1[start1];
                index++;
                start1++;
            }else{
                array3[index] = array2[start2];
                index++;
                start2++;
            }
        }
        //array2走完
        while (start1 <= end1){
            array3[index] = array1[start1];
            index++;
            start1++;
        }
        //array1走完
        while (start2 <= end2){
            array3[index] = array2[start2];
            index++;
            start2++;
        }
        return array3;
    }


    /**
     * 归并排序：
     * 时间复杂度：O(N*logN)
     * 空间复杂度：O(N)
     * 稳定性：稳定的排序
     * 如果 array[s1] <= array[s2] 不取等号  那么就是不稳定的排序
     *
     * 学过的排序 只有3个是稳定的：
     * 冒泡   插入   归并
     */
    //************归并排序*****************
    public void mergeSort(int[] array) {
        mergeSortInternal(array,0,array.length-1);
    }

    public void mergeSortInternal(int[] array,int low,int high) {
        if(low>=high) {
            return;
        }
        //int mid = (low+high) >>> 1;
        int mid = low + ((high-low) >>> 1);
        //左边
        mergeSortInternal(array,low,mid);
        //右边
        mergeSortInternal(array,mid+1,high);
        //合并
        merge(array,low,mid,high);
    }

    private void merge(int[] array,int low,int mid,int high) {
        int[] tmp = new int[high-low+1];
        int k = 0;//

        int s1 = low;
        int e1 = mid;
        int s2 = mid+1;
        int e2 =  high;

        while (s1 <= e1 && s2 <= e2) {
            if(array[s1] <= array[s2]) {
                tmp[k++] = array[s1++];
            }else {
                tmp[k++] = array[s2++];
            }
        }

        while (s1 <= e1) {
            tmp[k++] = array[s1++];
        }

        while (s2 <= e2) {
            tmp[k++] = array[s2++];
        }
        //拷贝tmp数组的元素 放入原来的数组array当中
        for (int i = 0; i < k; i++) {
            array[i+low] = tmp[i];
        }
    }


    //非递归归并排序
    public void mergeSort1(int[] array) {
        int nums = 1;//每组的数据个数
        while (nums < array.length) {
            //数组每次都要进行遍历,确定要归并的区间
            for (int i = 0; i < array.length; i += nums*2) {
                int left = i;
                int mid = left+nums-1;
                //防止越界
                if(mid >= array.length) {
                    mid = array.length-1;
                }
                int right = mid+nums;
                //防止越界
                if(right >= array.length) {
                    right = array.length-1;
                }
                //小标确定之后，进行合并
                merge(array,left,mid,right);
            }
            nums *= 2;
        }
    }


    //计数排序
    /**
     * 计数排序：
     * 时间复杂度：O(N)
     * 空间复杂度：O(M) M:代表 当前数据的范围900 - 999
     * 稳定性：当前代码是不稳定的，但是本质是稳定的
     *
     * 一般适用于 有n个数，数据范围是0-n之间的
     */
    public static void countingSort(int[] array) {
        int maxVal = array[0];
        int minVal = array[0];
        for (int i = 1; i < array.length; i++) {
            if(array[i] < minVal) {
                minVal = array[i];
            }
            if(array[i] > maxVal) {
                maxVal = array[i];
            }
        }
        //说明，已经找到了最大值和最小值
        int[] count = new int[maxVal-minVal+1];//默认都是0
        //统计array数组当中，每个数据出现的次数
        for (int i = 0; i < array.length; i++) {
            int index = array[i];
            //为了空间的合理使用 这里需要index-minVal  防止923-900
            count[index-minVal]++;
        }
        //说明，在计数数组当中，已经把array数组当中，每个数据出现的次数已经统计好了
        //接下来，只需要，遍历计数数组，把数据写回array
        int indexArray = 0;
        for (int i = 0; i < count.length; i++) {
            while (count[i] > 0) {
                //这里一定要加minVal，因为不一定就是i出现了count[i]
                array[indexArray] = i+minVal;
                count[i]--;//拷贝一个之后，次数也就少一个
                indexArray++;//下标得向后移动
            }
        }
    }

}
